import math
import random

def assign_cluster(x, centroids):
    min_distance = float('inf')
    closest_centroid = 0
    
    for i, centroid in enumerate(centroids):
        # 计算欧几里得距离
        distance = math.sqrt(sum((a - b) ** 2 for a, b in zip(x, centroid)))
        if distance < min_distance:
            min_distance = distance
            closest_centroid = i
    
    return closest_centroid

def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    """
    K均值聚类算法
    """
    centroids = random.sample(data, k)
    
    for _ in range(max_iterations):
        clusters = [[] for _ in range(k)]
        for point in data:
            cluster_idx = assign_cluster(point, centroids)
            clusters[cluster_idx].append(point)
        
        new_centroids = []
        for cluster_points in clusters:
            if cluster_points:
                new_center = [sum(dim) / len(cluster_points) for dim in zip(*cluster_points)]
                new_centroids.append(new_center)
            else:
                new_centroids.append(centroids[len(new_centroids)])
        
        movement = sum(math.sqrt(sum((a - b) ** 2 for a, b in zip(old, new)))
                     for old, new in zip(centroids, new_centroids))
        
        if movement < epsilon:
            break
            
        centroids = new_centroids
    
    return centroids, clusters

def main():
    data = [
        [1, 2], [1, 4], [1, 0],
        [4, 2], [4, 4], [4, 0],
        [8, 2], [8, 4], [8, 0]
    ]
    
    k = 3
    centroids, clusters = Kmeans(data, k)
    
    print("聚类中心:")
    for i, centroid in enumerate(centroids):
        print(f"中心 {i}: {centroid}")
    
    print("\n聚类结果:")
    for i, cluster in enumerate(clusters):
        print(f"聚类 {i} 有 {len(cluster)} 个点: {cluster}")

if __name__ == "__main__":
    main()  